#include "../Basics/BasicStruct.cpp"

// 翻转链表

// 遍历+头插

// 带头结点
List reverse(List list) {
    ListNode* p = list->next;
    list->next = NULL;
    while (p!=NULL) {
        ListNode* q = p->next;
        p->next = list->next;
        list->next = p;
        p = q;
    }
    return list;
}

// 不带头结点
List noHeadReverse(List list) {
    ListNode* p = list;
    ListNode* head = (ListNode*) malloc(sizeof(ListNode));
    head->next = NULL;
    while (p!=NULL) {
        ListNode* q = p->next;
        p->next = head->next;
        head->next = p;
        p = q;
    }
    return head->next;
}

int main() {
    List list = CreateList();
    List newList = noHeadReverse(list);
    PrintList(newList);
}